package exam.bak.meituan;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class P3 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int[] params = Arrays.stream(scanner.nextLine().trim().split(" ")).mapToInt((s -> Integer.parseInt(s))).toArray();
        int n = params[0];
        int k = params[1];
        //
        int[][] datas = new int[n][4];
        for (int i = 0; i < n; i++) {
            datas[i] = Arrays.stream(scanner.nextLine().trim().split(" ")).mapToInt((s -> Integer.parseInt(s))).toArray();
        }
        int[] maxResult = new int[1];
        bt(datas, k, 0, 0, new HashMap<Integer, Integer>(), maxResult);
        System.out.println(maxResult[0]);
    }


    public static void bt(int[][] datas, int k, int begin, int total, Map<Integer, Integer> map, int[] maxResult) {
        if (begin == datas.length) {//结束
            maxResult[0] = Math.max(maxResult[0], total);
        } else {
            //不选
            bt(datas, k, begin + 1, total - k, map, maxResult);
            //选
            int[] data = datas[begin];
            if (!map.containsKey(data[2])) {
                map.put(data[2], 0);
            }
            int tmp = total;
            if (map.get(data[2]) + 1 == data[3]) {
                tmp += data[0];
            } else {
                tmp += data[0] - data[1];
            }
            bt(datas, k, begin + 1, tmp, map, maxResult);
        }
    }
}
